package com.zp.self.module.level_4_算法练习.数据结构.数组;

/**
 * @author By ZengPeng
 */
public class 力扣_169_多数元素 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_169_多数元素().maxProfit(new int[]{3,2,3}));
        System.out.println(new 力扣_169_多数元素().maxProfit(new int[]{2,2,1,1,1,2,2}));
        System.out.println(new 力扣_169_多数元素().maxProfit(new int[]{8,8,7,7,7}));
    }

    /**
     * 题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
     *
     示例 1：
     输入：[3,2,3]
     输出：3

     示例 2：
     输入：[2,2,1,1,1,2,2]
     输出：2
     *
     * 分析：
     *      1.简单方法：遍历，并用HashMap记录每个数字出现的次数。 空间、时间 O(n)
     *      #大神解法：诸侯争霸  ，当前士兵数count  ,当前阵营 currentCamp  ，当阵营人数为0 换阵营。空间O(1)、时间 O(n)
     *      #大神解法：统计位众数，最后根据判断得出值：if(ones > zero) res = res|(1<<i);空间O(1)、时间 O(32*n)
     *      #排序，取出 第n/2 个元素 。 空间O(1)、时间 O(n*logn)
     *
     *
     * 边界值注意：
     *      1.
     **/
    public int maxProfit(int[] nums) {
        int count=1,currentCamp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==currentCamp) count++;
            else {
                if(count ==1)currentCamp = nums[++i];
                else count--;
            }
        }
        return currentCamp;
    }
}
